/*
 * @lc app=leetcode.cn id=148 lang=golang
 *
 * [148] 排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	m := middle(head)
	tmp := m
	m.Next = nil
	m = tmp
	left := sortList(head)
	right := sortList(m)

	return mergeTwoLinkedList(left, right)
}

func middle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	p, q := head, head
	for q.Next != nil || q.Next.Next != nil {
		p = p.Next
		q = q.Next.Next
	}

	return p
}

func mergeTwoLinkedList(l1, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}

	if l2 == nil {
		return l1
	}

	if l1.Val < l2.Val {
		l1.Next = mergeTwoLinkedList(l1.Next, l2)
		return l1
	} else {
		l2.Next = mergeTwoLinkedList(l1, l2.Next)
		return l2
	}
}

// @lc code=end

